\section{Problema 3: Transportes pesados}

\subsection{Introducción}

Una empresa que fabrica ladrillos tiene que distribuir su mercadería entre clientes ubicados en distintas ciudades. Todas las fábricas y las ciudades están unidas por rutas que necesitan repararse debido al peso de los camiones que circulan por ellas. Cada ruta tiene un costo de repavimentación asociado.

El problema consiste en indicar el conjunto de rutas que deben recorrer los camiones de manera tal de llevar los ladrillos a todos los clientes minimizando el costo de repavimentación total.

Por ejemplo:
\begin{verbatim}
INPUT: 
1 2 3
1 2 10
2 3 10
1 3 50

OUTPUT:
20 2 2 3 1 2 
\end{verbatim}

%PONER DIBUJITO




\subsection{Desarrollo}

Para modelar el problema, usamos una estructura de grafos en la cuál cada nodo representa una fábrica o un cliente, y las 
aristas la ruta que los une con su peso determinado (ver dibujito de introducción).

El objetivo según este modelo consiste en buscar un camino que conecte cada nodo cliente con alguna fábrica, de manera
que el peso total de las aristas sea mínimo. Esto tiene una gran semejanza con la búsqueda del árbol generador mínimo, 
con la diferencia de que lo que se busca es un \textbf{bosque} de árboles generadores mínimos. Es decir, el grafo puede
tener más de una componente conexa, dado que hay aristas que pueden ser innecesarias para llegar a la solución.

Por esto mismo decidimos hacer una adaptación del algoritmo de Kruskal\footnote{ver Cormen, T. and Leiserson, C.E. and Rivest, R.L. and Stein, C., \textsl{Introduction To Algorithms}, MIT-Pess, Cambridge, Massachusets, London, England. Capitulo 6: Graph Algoritm's, Sección 23.2: The algoritms of Kruskal and Prim}. Éste consiste básicamente en ir eligiendo las aristas de menor peso de manera que al agregarlas al grafo no se formen ciclos. Nuestro algoritmo contempla la misma lógica y se describe a continuación:


Tal como hace Kruskal en su implementación optimizada, las fábricas y los clientes se asocian a un \textsl{Disjoint-set}, es decir, a conjuntos que puedan ser identificados por uno de sus miembros (que está destacado)\footnote{ver Cormen, T. and Leiserson, C.E. and Rivest, R.L. and Stein, C., \textsl{Introduction To Algorithms}, MIT-Pess, Cambridge, Massachusets, London, England. Capitulo 6: Graph Algoritm's, Sección 21.1: Disjoint-set operations}. Estos conjuntos contienen a las Fábricas y Clientes, que están representadas por la estructura \textit{Nodo}:

\begin{verbatim}

typedef struct Nodo{
	Nodo *proximo;
	Nodo *final\_lista;
	Nodo *raiz;
	bool tiene\_fabrica;
	int cantidad\_de\_elementos;
} Nodo;

\end{verbatim}

A través de la estructura \textit{Nodo} vamos a implementar los \textsl{Disjoint-sets} como listas enlazadas, en la cual \textit{*proximo} va a ser un puntero al proximo elemento del conjunto, \textit{*final\_lista} va a ser un punter al último elemento (el nodo que voy a usar para unir un conjunto nuevo) y \textit{*raiz} va a marcar al elemento distintivo del conjunto (todos los elementos del conjunto apuntan a la misma raíz). Los valores de \textit{tiene\_fabrica} (que indica si en el conjunto ya hay alguna fábrica) y \textit{cant\_elementos} (que me marca la cantidad de elementos del conjunto) sólo van a ser utilizados para la raíz de cada conjunto. Para el resto, si quiero saber esta información, bastará con acceder al puntero a la raíz y preguntarle a la raíz.

Las rutas se representan con la estructura \textit{Ruta}, que contiene el dato de las ciudades que une y su peso.

Todas las rutas son ordenadas en un min\_heap\footnote{El min\_heap se implementa a través de la función make\_heap de la librería algorithms, que toma tres parámetros: un iterador al comienzo de la lista, un iterador que apunta al final y una función booleana que compara dos elementos. En este caso, la función booleana es \textit{trd\_order} compara la longitud de las rutas implementadas mediante un struct. Para más referencias, ver http://www.cplusplus.com/reference/algorithm/make\_heap/}. El objetivo de esta estructura es recorrer las rutas en orden de menor a mayor según el costo de pavimentación.

Para cada ruta se van a verificar las siguientes condiciones: que al seleccionar esa ruta como parte de mi solución no se formen ciclos y que tampoco esté uniendo dos componentes tales que ambas tengan una fábrica. Si la ruta seleccionada cumple con ambos requisitos, la guardo en un vector \textit{resultado} y luego junto los nodos enlazados de las dos componentes conexas de esas ciudades entre sí. Finalmente actualizo la variable \textit{tiene\_fabrica} y \textit{cantidad\_de\_elementos}, pero sólo para la raíz de la componente conexa (o el elemnto que lo identifica).

A continuación se muestra un ejemplo del funcionamiento:

\centerline{\includegraphics{algoritmo1.png}}
\centerline{\includegraphics{algoritmo2.png}}
\centerline{\includegraphics{algoritmo3.png}}
\centerline{\includegraphics{algoritmo4.png}}
\centerline{\includegraphics{algoritmo5.png}}
\centerline{\includegraphics{algoritmo6.png}}
\centerline{\includegraphics{algoritmo7.png}}

Este algoritmo toma las principales características del algoritmo de Kruskal, ya que cada ciclo toma la ruta de menor peso y se fija que al agregarla no se produzcan ciclos. La variante implementada chequea además que las dos componentes conexas que la ruta une no tengan ambas una fábrica, ya que de ser así, gastar una ruta en unirlas sería un costo innecesario. Como consecuencia de esta variante, nuestro algoritmo no da como resultado un árbol generador mínimo, sino un bosque generador mínimo tal que para cada árbol del bosque haya una y exactamente una fábrica.


\subsubsection{Código Fuente}

Incluimos a continuación el ciclo principal del código fuente de nuestro algoritmo:

\begin{verbatim}
 	for (int k = 0; k < rutas.size(); k++) {
		//Levanto una ruta	
		primera_ciudad = rutas.front().ciudad_inicio;
		segunda_ciudad = rutas.front().ciudad_fin;
		
		primera_ciudad--;
		segunda_ciudad--;
		
		//Chequeo si no estan juntas o si ambas ya tienen una fábrica
		if((ciudades[primera_ciudad]->raiz != ciudades[segunda_ciudad]->raiz) && 
		(!(ciudades[primera_ciudad]->raiz->tiene_fabrica && 
		ciudades[segunda_ciudad]->raiz->tiene_fabrica))){
		
			raiz1 = ciudades[primera_ciudad]->raiz;
			raiz2 = ciudades[segunda_ciudad]->raiz;
			
			//Me fijo cual es la de longitud más corta	
			if(raiz1->cantidad_de_elementos < raiz2->cantidad_de_elementos) {
				raizAux = raiz1;
				raiz1 = raiz2;
				raiz2 = raizAux;
			}
			
			//Pongo la lista más pequeña atrás de la más grande y actualizo la raiz de la más grande
			(raiz1->final_lista)->proximo = raiz2;
			raiz1->final_lista = raiz2->final_lista;
			raiz1->tiene_fabrica = (raiz1->tiene_fabrica || raiz2->tiene_fabrica);
			raiz1->cantidad_de_elementos += raiz2->cantidad_de_elementos; 
			
			nodoAux = raiz2;
			
			//Actualizo los elementos de la lista más pequeña que estoy agregando
			for(int h = 0; h < raiz2->cantidad_de_elementos; h++) {
				nodoAux->raiz = raiz1;
				nodoAux = nodoAux->proximo;
			}
			
			resultado.push_back(rutas.front());
			pop_heap(rutas.begin(), rutas.end(), trd_order);
			rutas.pop_back();
		} else {
			pop_heap(rutas.begin(), rutas.end(), trd_order);
			rutas.pop_back();
		}
	}
	
	return resultado;
\end{verbatim}




\subsection{Correctitud}

La demostración de correctitud del algoritmo va a estar dividida en dos grandes partes: que la suma de las rutas seleccionadas es mínima y que todos los clientes tienen algún camino que les permita llegar a una fábrica.

\subsubsection{Suma mínima}

El algoritmo transforma el vector de rutas en un min\_heap. Luego las levanta de ésta estructura de manera tal que el heap siempre se preserve. Por lo tanto podemos garantizar por las propiedades del min\_heap (ver nota al pie en la sección anterior) que tomamos las rutas en orden de menor a mayor según el valor de su longitud. Esto nos garantiza que si nuestro algoritmo busca satisfacer cierta condición (que todos los clientes estén en alguna componente conexa sin ciclos con exactamente una fábrica), la primer instancia de nuestro algoritmo que haya logrado este objetivo se habrá alcanzado utilizando las rutas de menor valor (porque se recorrieron en ese orden).

Queremos ver ahora, que no tomamos más rutas que las estrictamente necesarias. Para esto basta analizar la condición que le pide el algoritmo a una ruta para ponerla dentro del vector resultado. Esta es basicamente la siguiente:

\begin{verbatim}
 
 		if((ciudades[primera\_ciudad]->raiz != ciudades[segunda\_ciudad]->raiz) && 
		  (!(ciudades[primera\_ciudad]->raiz->tiene\_fabrica && 
		  ciudades[segunda\_ciudad]->raiz->tiene\_fabrica))){
		  
		  ...
		  
		  }
  
\end{verbatim}

En lenguaje coloquial, esto significa que sólo va a procesar una ruta si los elementos distintivos de la componente conexa de cada ciudad no son iguales (las ciudades no están ya unidas) o si alguna de las dos componentes conexas no tiene fábrica. La utilidad de la primera condición salta a la vista: si dos ciudades ya tienen un camino que los une no es necesario gastar la pavimentación de una ruta más en unirlas. La utilidad de la segunda condición es la siguiente: dado que sólo nos importa que cada cliente esté unido a alguna fábrica y no necesariamente que todos los clientes estén unidos entre sí, si dos componentes conexas separadas ya tienen cada una una fábrica conectada repavimentar una ruta para unirlas es un desperdicio.
%
Por lo tanto, podemos garantizar que el algoritmo no selecciona más rutas que las estrictamente necesarias y que por otro lado, las va seleccionando de menor a mayor, cosa de intentar satisfacer las condiciones que requiere el problema con las rutas de menor valor posible.

\subsubsection{Todos los clientes tienen una fábrica}

Nuestro algoritmo recorre una a una todas las aristas que tiene nuestro grafo. Cada vez que encuentra una componente conexa tal que una tiene una fábrica asignada y la otra no o tal que ninguna tenga una fábrica asignada, las une formando una única componente conexa. Supongamos que existe una ruta tal que es la ruta de menor valor que une una componente conexa sin fábricas con otra componente conexa pero que esa ruta no está entre los resultados que seleccionó nuestro algoritmo. Como nuestro algoritmo recorre todas las rutas, la única manera de que al evaluar esa ruta no la hubiera seleccionado es que el algoritmo hubiera unido esas componentes conexas utilizando otra ruta con anterioridad. Pero si eligió otra ruta con anterioridad, eso quiere decir que esa ruta tenía menor longitud que la ruta que descartó. Esto es absurdo, porque por hipótesis planteamos que la ruta que descartó era la de menor valor de entre las que unían las dos componentes conexas antes mencionadas. La contradicción nace de suponer que 
existe una ruta tal que es la ruta de menor valor que une una componente conexa sin fábricas con otra componente conexa pero que no está en el resultado del algoritmo.

\subsection{Análisis de complejidad}\label{complejidad3}

\subsubsection{Pseudocódigo}

Sean $m$ la cantidad de rutas, $n$ la cantidad de ciudades, $c$ la cantidad de clientes y $f$ la cantidad de fábricas, el pseudocódigo del algoritmo con su complejidad es el siguiente:

\begin{algorithm}

    \SetKwInOut{Input}{input}
    \SetKwInOut{Output}{ouput}
    \SetKwComment{Complejidad}{\color{Blue}$\rhd$ $\mathcal O($}{\color{Blue}$\mathcal )$}
    \SetKwComment{SubComplejidad}{\color{Red}$\square$ $\mathcal O($}{\color{Red}$\mathcal )$}
    \SetKwComment{SubSubComplejidad}{\color{Fuchsia}$\fullmoon$ $\mathcal O($}{\color{Fuchsia}$\mathcal )$}
    \SetKwComment{ComplejidadTotal}{\color{Blue}Complejidad total $\rhd$ $\mathcal O($}{\color{Blue}$\mathcal )$}
    \SetKwComment{SubComplejidadTotal}{\color{Red}Complejidad total $\square$ $\mathcal O($}{\color{Red}$\mathcal )$}
    \SetKwComment{SubSubComplejidadTotal}{\color{Fuchsia}Complejidad total $\fullmoon$ $\mathcal O($}{\color{Fuchsia}$\mathcal )$}

    \SetKwData{A}{A}
    \SetKwData{n}{n}

    \Input{Vector de ruta \texttt{rutas}, Entero \texttt{fabricas}, Entero \texttt{clientes}}
    \Output{Vac\'io}
    % \BlankLine
    make\_min\_heap de las rutas \Complejidad*[r]{\color{blue}$m$}
    armar una componente conexa (representada por un nodo) para cada cliente y fabrica \Complejidad*[r]{\color{blue}$n$}
    \For(\Complejidad*[f]{\color{blue}$m$}){$ruta\_i$ con $[$ i $|$ $0 ... m$ $)$}{    
      levanto la ruta del heap \Complejidad*[r]{\color{blue}$log n$}
    	\If{la $ciudad\_inicio$ de la ruta no esta en la misma componente conexa que la $ciudad\_fin$ y no están unidas ambas a una fábrica}{
    	    agrego la componente conexa más chica detrás de la más grande \Complejidad*[r]{\color{blue}$1$}
    	    actualizo los elementos la componente más chica \Complejidad*[r]{\color{blue}$log\ n$ como mucho para cada nodo al finalizar el ciclo}
    	    actualizo la raiz con la cantidad de elementos que le sume y si tiene fábrica o no \Complejidad*[r]{\color{blue}$1$}
    	    agrego la ruta a la lista de resultados \Complejidad*[r]{\color{blue}$1$}
    	    elimino la ruta del vector \texttt{rutas} \Complejidad*[r]{\color{blue}$1$}
       	\Else{elimino la ruta del vector \texttt{rutas} \Complejidad*[r]{\color{blue}$1$}}
    }
    }
    
    imprimo el resultado por pantalla
    
    \caption{Ejercicio 1 - Pseudocódigo y Complejidad}
    \label{pseudocodigo1}
\end{algorithm}

El análisis de complejidad nos muestra una complejidad similar al algoritmo de Kruskal que es de $O(m log(n))$. El armado del heap más el arreglo necesario para mantenerlo cuesta $O(m log(m))$. Por otro lado, el ciclo que evalúa si una ruta va dentro de las respuestas o no se llama una vez para cada ruta. Dentro de este ciclo, todas las operaciones cuestan $O(1)$ con excepción de unir las componentes conexas, lo que implica actualizar el puntero al elemento distintivo del conjunto de nodos que ya fueron unidos. Vamos a demostrar que esta operación es del orden de $O(N log(N))$ donde N es la cantidad de nodos (o ciudades) que se le pasan por parámetro al algoritmo.

Vamos a asumir un peor caso en el cual se realizan la máxima cantidad de operaciones de union de componentes conexas posible. Queremos contar para este caso, cuantas veces, como máximo, voy a necesitar actualizar cada elemento. Cada elemento será actualizado sólo cuando la componente a la que pertenece se una a otra componente más grande. Como resultado de esto, esta componente, en el peor de los casos, duplicará su tamaño. Esto nos permite establecer una cota de $log_{2}(n)$ a la cantidad de veces que el elemento se va a actualizar. Como tengo n elementos y el ciclo se corre m veces, podemos establecer una cota de complejidad para el ciclo del orden de $O((n+m) log(n))$. Sin embargo, como sabemos que el grafo original era una componente conexa, podemos deducir que $m \geq n$ y por lo tanto $2*m \geq (n+m)$ con lo que la complejidad del ciclo está dentro del orden de $O(m log(n))$.

Como podemos acotar m por $n^{2}$, la complejidad del ordenamiento de las rutas de $O(m log(m))$ podemos acotarla por $O(m log(n^{2})) = O(m log(n))$. Como además la cantidad de ciudades es en el peor de los casos 2 veces la cantidad de clientes, podemos afirmar que nuestro algoritmo tiene una complejidad del orden de $O(R log(C))$ donde R es la cantidad de rutas y C la cantidad de clientes.


\subsection{Análisis de casos}

\subsection{Test de performance}

\subsection{Compilar y ejecutar}\label{ejecucion3}
